package subject_set.top101;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}
/**
 * @author haomin
 * @date 2022/11/01 18:23
 **/
public class BM25 {
    public class Solution {
        List<Integer> list = new LinkedList<>();
        public int[] postorderTraversal (TreeNode root) {
            postOrder(root);
            return list.stream().mapToInt(Integer::intValue).toArray();
        }
        private void postOrder(TreeNode root){
            if(root == null) return;
            postOrder(root.left);
            postOrder(root.right);
            list.add(root.val);
        }
    }
    public class Solution2 {
        public int[] postorderTraversal (TreeNode root) {
            if(root == null) return new int[0];
            List<Integer> list = new ArrayList<>();
            Deque<TreeNode> s = new LinkedList<>();
            TreeNode pre = null;
            while(!s.isEmpty() || root != null){
                while(root != null) {
                    s.push(root);
                    root = root.left;
                }
                root = s.pop();
                if(root.right == null || pre == root.right){
                    list.add(root.val);
                    pre = root;
                    root = null;
                }else {
                    s.push(root);
                    root = root.right;
                }
            }
            return list.stream().mapToInt(Integer::intValue).toArray();
        }
    }
}